#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int minimumCost(vector<int>& cost) {
        sort(cost.begin(), cost.end(), greater<int>());
        int flag = 0;
        int sum = 0;
        int DSum = 0;
        for (int i = 0; i < cost.size(); ++i)
        {
            if (cost[i] == -1)
                continue;
            if (flag == 1)
            {
                DSum += cost[i];
                int j = 0;
                for (j = i + 1; j < cost.size(); ++j)
                {
                    if (cost[j] <= DSum)
                    {
                        cost[j] = -1;
                        break;
                    }
                }
                if (j == cost.size())
                    flag = -999;
                else
                    flag = 0;
                DSum = 0;
            }
            else
            {
                DSum += cost[i];
                ++flag;
            }
            sum += cost[i];
        }

        return sum;
    }
};